package cn.xaut.数组;

import java.util.Arrays;

public class demo75 {

    // 计数排序
    public void sortColors(int[] nums) {

        int[] count = new int[3];
        for (int x : nums) 
            count[x] ++;

        int index = 0;
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                nums[index++] = i;
            }
        }
    }

    static void swap(int[] nums, int i, int j) {
        assert i >= 0 && i < nums.length && j >= 0 && j < nums.length;
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    
    // 三路快排
    // 错误的方法 ↓
    public void sortColors2(int[] nums) {
        
        int len = nums.length;
        int step = len / 3; // 步长
        int l = 0, r = len - 1;
        int li = 0, mi = li + step, ri = mi + step;

        for (int i = 0; i < len; i++) {
            int t = nums[i] / 2;
            while (t == 0) {
                swap(nums, li, i);
                li ++;
            }
            while (t == 1) {
                swap(nums, mi, i);
                mi ++;
            }
            while (t == 2) {
                swap(nums, ri, i);
                ri ++;
            }
        }
    }

    // 三路快排
    // 双指针
    public void sortColors3(int[] nums) {
        
        int zero = -1;          // nums[0...zero] == 0
        int two = nums.length;  // nums[two...n-1] == 0

        for (int i = 0; i < two;) {
            if (nums[i] == 0) {
                zero ++;
                swap(nums, zero, i);
                i ++;
            } else if (nums[i] == 1) {
                i++;
            } else {    // nums[i] == 2
                two --;
                swap(nums, two, i);
            } 
        }
    }

    public static void main(String[] args) {

        int[] nums = new int[]{2, 0, 2, 1, 1, 0};
        int[] nums2 = new int[]{2, 2, 1, 0, 1, 0};
        new demo75().sortColors3(nums);
        new demo75().sortColors3(nums2);
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(nums2));
    }
}
